EVENTO
Algoritmos Quânticos para Problemas em Teoria de Grupos Computacional
Tipo de evento: Defesa de Tese de Doutorado
Neste trabalho apresentamos um novo algoritmo quântico eficientepara o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p \rtimes Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(\sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é \Omega(\sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m \rtimes Z_p, com m, N inteiros positivos e N fatorado de forma especial.
Data Início: 28/08/2009 Hora: 10:00 Data Fim: 28/08/2009 Hora: 12:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Demerson Nunes Gonçalves - Laboratório Nacional de Computação Científica - LNCC
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Carlile Campos Lavor - Universidade Estadual de Campinas - IMECC/UNICAMP Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC Guilherme Augusto de La Rocque Leal - IM-UFRJ - UFRJ Paulo César Marques Vieira - Laboratório Nacional de Computação Científica - LNCC Raul José Donangelo - UFRJ - UFRJ Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: Adilson Gonçalves - IM-UFRJ - IM-UFRJ Jauvane Cavalcante de Oliveira - Laboratório Nacional de Computação Científica - LNCC
